166

13

Useful Algorithms

so that

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout ^∂S2

∂zkμ

= 2B⁻¹

N,N

Σ

i, j=1

[^∼Ei j −Ei j] ^{∂∼Ei j}

∂zkμ

.

(13.19)

Using Eq. (13.14) gives

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout^{∂∼Ei j}

∂zkμ

= ^∼E⁻¹

i j

∼

M

Σ

ν=1

[aiν −a jν][δikδνμ −δ jkδνμ] ,

(13.20)

where the Kronecker delta delta Subscript i kδik, as usual, equals 1 for i equals ki = k and 0 for i not equals ji /= j. Then,

after some algebra,

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout ^∂S2

∂zkμ

= 4B⁻¹

N

Σ

j=1

[^∼Ekj −Ekj]^∼E⁻¹

kj ^{[akμ −a jμ] .}

(13.21)

Hence, by integration, the estimated vectors are given by

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout∧zkμ = zkμ + α ^∂S2

∂zkμ

,

(13.22)

whereModifyingAbove z With caret Subscript k mu∧zkμ is the next iteration, and minimizing the stress function provides the scale

and direction for the propagation, and alphaα provides the iteration increment, typically

fixed asupper N Superscript negative 3N ⁻³. Iteration continues until the stress function reaches zero or some lower

threshold. Note that the value of upper M overTilde ^∼

M used to reconstruct the vector space need not be

the same as the original space dimension upper MM.

An important application of MDS is to seriation—the correct ordering of an

assembly of objects along one dimension, given merely the presence or absence a

certain number of features in each object. ⁹ These data are arranged in a Boolean

incidence matrix, with the rows corresponding to the objects and the columns to

the features, a “1” corresponding to the presence of a feature in an object. The

characteristic pattern to be expected is that in every column, the 1s are clumped

together, or, if there are multiple representations of features in the objects, in every

column their number increases to a maximum and then decreases. Evidently, this

can be achieved by appropriate rearrangement of the order of the rows. All of the

relevant information is contained in the similarity matrix (in the sense of similar to

the serial ordering), in which the element left parenthesis i comma j right parenthesis(i, j) is the number of features common

to the iith and j jth objects.

9 This was famously applied by Kendall (1970) to the problem of chronology of early Egyptian

tombs found at a certain site. The features in that case are artisanal artefacts characteristic of a

certain epoch found in the tombs.